package dp;

import java.util.*;

/**
 * @author ZJX
 * @version 1.0
 * @descption
 * @since 2025/10/8 19:20
 */
public class Aura {
    // 力扣  53  极高
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) return nums[0];
        int cur = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            max = Math.max(max, cur);
        }
        return max;
    }

    //    爬楼梯
    public int climbStairs(int n) {
        if (n == 0 || n == 1 || n == 2) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 力扣 198 打家劫舍 高
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1]; // dp[i] 表示第i个房子的获得的最大金额
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[n];
    }

    //    力扣 121 高
    public int maxProfit(int[] prices) {
        int cur = prices[0];
        int max = 0;
        for (int price : prices) {
            if (cur > price) {
                cur = price;
            } else {
                max = Math.max(max, price - cur);
            }
        }
        return max;
    }

    public boolean canPartition(int[] nums) {
        int total = 0;
        int max = nums[0];
        for (int num : nums) {
            total += num;
            if (num > max) {
                max = num;
            }
        }
        if (total % 2 == 1) return false;
        int target = total / 2;
        if (max > target) return false;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                if (dp[i - num]) {
                    dp[i] = true;
                }
                if (dp[target]) {
                    return true;
                }
            }
        }
        return false;
    }

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 边界条件1：target的绝对值超过sum，无解
        if (Math.abs(target) > sum) {
            return 0;
        }
        // 边界条件2：(target + sum)必须为偶数，否则p不是整数，无解
        if ((target + sum) % 2 != 0) {
            return 0;
        }

        int n = (target + sum) / 2;
        // 边界条件3：n为负数时，无解（因为p不能为负）
        if (n < 0) {
            return 0;
        }

        int[] dp = new int[n + 1];
        dp[0] = 1; // 凑出和为0的方案数：不选任何数

        for (int num : nums) {
            // 0-1背包：倒序遍历，避免重复选
            for (int i = n; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }

        return dp[n];
    }

    /* ---------------------------  完全背包  -------------------------------*/

    /*

     完全背包遍历顺序的选择口诀:
        求组合（不看顺序）：先物品，后容量；
        求排列（看顺序）：先容量，后物品；
        求最值 / 存在性：顺序随意（推荐先物品后容量）。

     */

    //    力扣 322
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; // 到 amount 最小需要多少个硬币
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

    //    力扣518
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1]; // dp[i]为i金额下的组成方式
        dp[0] = 1;
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        return dp[amount];
    }

    //    力扣279
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) {
            int square = i * i;
            for (int j = square; j <= n; j++) {
                if (dp[j - square] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - square] + 1);
                }
            }
        }
        return dp[n];
    }

    // 力扣983
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length - 1];
        int[] dp = new int[lastDay + 1]; // dp 表示旅行i天所花费的最小金额
        Set<Integer> travelDays = new HashSet<>();
        for (int day : days) {
            travelDays.add(day);
        }
        dp[0] = 0;
        for (int i = 1; i <= lastDay; i++) {
            if (!travelDays.contains(i)) {
                dp[i] = dp[i - 1]; // 不旅游 不花费
            } else {
                int cost1 = dp[i - 1] + costs[0];
                int cost7 = dp[Math.max(0, i - 7)] + costs[1];
                int cost30 = dp[Math.max(0, i - 30)] + costs[2];
                dp[i] = Math.min(cost7, Math.min(cost1, cost30));
            }
        }
        return dp[lastDay];
    }

    //    力扣 139
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];  // dp[i]：前i个字符能否被拼接
        dp[0] = true;  // 空字符串可被拼接

        // 先遍历容量（每个子串长度）
        for (int i = 1; i <= n; i++) {
            // 再遍历物品（每个单词）
            for (String word : wordDict) {
                int wordLen = word.length();

                // 只有当子串长度 >= 单词长度时，才可能匹配
                if (i >= wordLen) {
                    // 1. 取出当前子串（前i个字符的最后wordLen个字符）
                    String currentSub = s.substring(i - wordLen, i);
                    // 2. 判断子串是否和单词匹配
                    boolean isSubMatchWord = currentSub.equals(word);
                    // 3. 判断去掉当前单词后，剩下的左半部分能否被拼接
                    boolean isLeftPartValid = dp[i - wordLen];

                    // 两个条件都满足，说明前i个字符能被拼接
                    if (isSubMatchWord && isLeftPartValid) {
                        dp[i] = true;
                        break;  // 找到一个匹配即可，无需检查其他单词
                    }
                }
            }
        }

        return dp[n];
    }

    //    力扣343
    public int integerBreak(int n) {
        int[] dp = new int[n + 1]; // 最大乘积
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }

    //    力扣 246 丑数
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; i++) {
            int num1 = dp[p2] * 2;
            int num2 = dp[p3] * 3;
            int num3 = dp[p5] * 5;
            dp[i] = Math.min(num2, Math.min(num1, num3));
            if (dp[i] == num1) p2++;
            if (dp[i] == num2) p3++;
            if (dp[i] == num3) p5++;
        }
        return dp[n];
    }

    /* ------------------------------ 子数组系列 --------------------------------------*/

    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }

    //    力扣 560
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int sum = 0;
        int count = 0;
        for (int num : nums) {
            sum += num;
            // 检查是否存在某个前缀和使得 sum - preSum == k
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }

            // 更新当前前缀和出现次数
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }

    public int maxProduct(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        int ret = nums[0];
        int max = nums[0];
        int min = nums[0];
        for (int i = 1; i < n; i++) {
            int preMax = max;
            int preMin = min;
            min = Math.min(nums[i], Math.min(preMax * nums[i], preMin * nums[i]));
            max = Math.max(nums[i], Math.max(preMax * nums[i], preMin * nums[i]));
            ret = Math.max(ret, max);
        }
        return ret;
    }

    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // 多开一行一列作为虚拟边界
        int[][] dp = new int[m + 1][n + 1];  //dp[i][j]   以 nums1[i] 结尾 和 nums2[j] 结尾的最长公共连续子数组的长度
        int maxLen = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                }
            }
        }
        return maxLen;
    }

    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int n = nums.length;
        int zeroLen = 0;
        int maxLen = 0;
        for (int right = 0; right < n; right++) {
            if (nums[right] == 0) {
                zeroLen++;
            }
            while (zeroLen > k) {
                if (nums[left] == 0) {
                    zeroLen--;
                }
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }


    /* ---------------------------------------  二维网格  ----------------------------------------------*/

    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n]; // dp[i][j] 表示从(0,0)到(i,j) 的不同种方法
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if (m == 0) return 0;
        int n = obstacleGrid[0].length;

        // 起点或终点有障碍物
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (obstacleGrid[i - 1][j - 1] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j] + frame[i - 1][j - 1], dp[i][j - 1] + frame[i - 1][j - 1]);
            }
        }
        return dp[m][n];
    }

    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;
        if (n == 0) return 0;

        int[][] dp = new int[m + 1][n + 2]; // 列数+2，避免j+1越界（j最大为n时，j+1=n+1仍有效）

        // 初始化第一行（dp[1][j] 对应 matrix[0][j-1]，因为第一行的路径和就是自身）
        System.arraycopy(matrix[0], 0, dp[1], 1, n);


        // 填充dp数组（从第2行开始，对应矩阵第1行及以下）
        for (int i = 2; i <= m; i++) { // i=2 对应矩阵的第1行（下标从0开始）
            for (int j = 1; j <= n; j++) { // j 对应矩阵的第j-1列
                // 上一行可能的来源：左上方（j-1）、正上方（j）、右上方（j+1）
                int topLeft = dp[i - 1][j - 1];
                int top = dp[i - 1][j];
                int topRight = dp[i - 1][j + 1];

                // 取上一行三个方向的最小值（处理边界：j=1时没有左上方，j=n时没有右上方）
                int minPrev;
                if (j == 1) {
                    // 左边界：只能从正上方或右上方来
                    minPrev = Math.min(top, topRight);
                } else if (j == n) {
                    // 右边界：只能从左上方或正上方来
                    minPrev = Math.min(topLeft, top);
                } else {
                    // 中间列：三个方向取最小
                    minPrev = Math.min(topLeft, Math.min(top, topRight));
                }

                // 当前路径和 = 上一行最小值 + 当前矩阵元素值
                dp[i][j] = minPrev + matrix[i - 1][j - 1];
            }
        }

        int ret = Integer.MAX_VALUE;
        for (int j = 1; j <= m; j++) {
            ret = Math.min(ret, dp[m][j]);
        }
        return ret;
    }

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
//        初始化第一行
        for (int j = 1; j <= n; j++) {
            dp[1][j] = dp[1][j - 1] + grid[0][j - 1];
        }
//        初始化第一列
        for (int i = 1; i <= m; i++) {
            dp[i][1] = dp[i - 1][1] + grid[i - 1][0];
        }
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = grid[i - 1][j - 1] + Math.min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        //  dp[i][j] 表示 到达第 i 行第 j 列的最小和
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i - 1][j - 1], dp[i - 1][j]);
            }
            dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = dp[n - 1][0];
        for (int j = 1; j < n; j++) {
            minTotal = Math.min(minTotal, dp[n - 1][j]);
        }
        return minTotal;
    }

    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int len = 0;
        int[][] dp = new int[m][n];  // 以矩阵中 (i,j) 位置为右下角的 最大正方形的边长。
//        第一列
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                len = 1;
            }
        }
//        第一行
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
                len = 1;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                    len = Math.max(len, dp[i][j]);
                }

            }
        }
        return len * len;
    }

    /* --------------------------------  状态机 DP（股票系列） --------------------------------------------*/

    public int maxProfit121(int[] prices) {
        int cur = prices[0];
        int max = 0;
        for (int price : prices) {
            if (cur > price) {
                cur = price;
            } else {
                max = Math.max(max, price - cur);
            }
        }
        return max;
    }

    public int maxProfit122(int[] prices) {
        int cur = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                max += (prices[i] - prices[i - 1]);
            }
        }
        return max;
    }

    public int maxProfit714(int[] prices, int fee) {
        int n = prices.length;
        int buy = prices[0];
        int profit = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] < buy) {
                buy = prices[i];
            } else if (prices[i] > buy + fee) {
                profit += prices[i] - buy - fee;
                buy = prices[i] - fee; // 核心
            }
        }
        return profit;
    }

    public int minCost(int[][] costs) {
        int n = costs.length;
        int[][] dp = new int[n][3]; // 红 蓝 绿 三种颜色
        dp[0][0] = costs[0][0]; // 红色
        dp[0][1] = costs[0][1]; // 绿色
        dp[0][2] = costs[0][2]; // 蓝色
        for (int i = 1; i < n; i++) {
            dp[i][0] = costs[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = costs[i][1] + Math.min(dp[i - 1][2], dp[i - 1][0]);
            dp[i][2] = costs[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
        }
        return Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2]));
    }

    public int maxProfit309(int[] prices) {
        int n = prices.length;
        if (n == 1) return 0;
        return 0;
    }

}

